package com.hy.treeNode3;

import com.hy.treeNode.TreeNode;

import java.util.Stack;

public class SumOfLeftLeaves {

    /**
     * 404.左叶子之和
     * 力扣题目链接
     *
     * 计算给定二叉树的所有左叶子之和。
     *
     * 思路
     * 首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。
     *
     * 因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子
     *
     * 递归法
     * 递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。。
     *
     * 递归三部曲：
     *
     * 1. 确定递归函数的参数和返回值
     * 判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
     * 使用题目中给出的函数就可以了。
     *
     * 2. 确定终止条件
     * 依然是
     * if (root == NULL) return 0;
     *
     * 3. 确定单层递归的逻辑
     * 当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
     *
     * @param root
     * @return
     */
    // 递归
    public int sumOfLeftLeaves2(TreeNode root){
        int res = 0;
        if (root == null){
            return res;
        }
        //左子树
        int leftLeaveSum = sumOfLeftLeaves2(root.left);
        //右子树
        int rightLeaveSum = sumOfLeftLeaves2(root.right);

        int midLeaveSum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            midLeaveSum = root.left.val;
        }
        // 中间节点
        res = midLeaveSum +leftLeaveSum + rightLeaveSum;
        return res;
    }

    // 迭代
    public int sumOfLeftLeaves(TreeNode root){
        int res = 0;
        Stack<TreeNode> st = new Stack<>();
        if (root == null){
            return res;
        }
        st.push(root);
        while (!st.isEmpty()){
            TreeNode node = st.pop();
            if (node.left != null && node.left.left == null && node.left.right  == null){
                res += node.left.val;
            }

            if (node.right != null){
                st.push(node.right);
            }
            if (node.left != null){
                st.push(node.left);
            }
        }
        return res;
    }


    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        SumOfLeftLeaves leaves = new SumOfLeftLeaves();
        System.out.println("左子树节点和 (迭代)："+leaves.sumOfLeftLeaves(root));
        System.out.println("左子树节点和 (递归)："+leaves.sumOfLeftLeaves2(root));


    }
}
